package leetcode.code035.SearchInsertPosition;

/**
 * [1,3] 2
 *
 * @author CaoYu
 * @date 2021年8月12日
 * @description
 */
public class Solution2 implements ISearchInsertPosition {

	@Override
	public int searchInsert(int[] nums, int target) {
		if (target < nums[0]) {
			return 0;
		}

		int len = nums.length;
		if (target > nums[len - 1])
			return len;
		int left = 0;
		int right = len - 1;
		int midle = 0;
		int ans = 0;
		// 可以撞到左边界，右边界-1，
		while (left <= right) {// 不带=的话 [1] 1,奇数midle是答案的情况收集不到
			midle = left + (right - left) / 2;
			if (nums[midle] == target) {
				return midle;
			}
			if (nums[midle] > target) {
				ans = midle;//最近一个比目标大的坐标
				right = midle - 1;
			} else {
				left = midle + 1; // [1,3] 2
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
//		so.test1();
		so.test2();
//		so.test3();
//		so.test4();
	}

//	输入: nums = [1,3,5,6], target = 5
//	输出: 2
	public void test1() {
		int[] nums = { 1, 3, 5, 6 };
		int target = 5;
		int output = 2;
		this.myDebug(nums, target, output);
	}

	private void myDebug(int[] nums, int target, int output) {
		int res = this.searchInsert(nums, target);
		System.out.println(res + " " + (res == output));
	}

//	输入: nums = [1,3,5,6], target = 2
//	输出: 1
	public void test2() {
		int[] nums = { 1, 3, 5, 6 };
		int target = 2;
		int output = 1;
		this.myDebug(nums, target, output);
	}

//	输入: nums = [1,3,5,6], target = 7
//	输出: 4
	public void test3() {
		int[] nums = { 1, 3, 5, 6 };
		int target = 7;
		int output = 4;
		this.myDebug(nums, target, output);
	}

//	输入: nums = [1,3,5,6], target = 0
//	输出: 0
	public void test4() {
		int[] nums = { 1, 3, 5, 6 };
		int target = 0;
		int output = 0;
		this.myDebug(nums, target, output);
	}

}
